This invention relates to an automatic routing method for determining paths for bus signals in an LSI, and in particular to an automatic routing method, which is suitable for an LSI designed according to the building block scheme, by which rectangular blocks of arbitrary size are arranged, or to the standard cell scheme, by which rectangular cells are arranged.
The bus signals play a role by the fact that a plurality of signals such as address signals, data signals, etc. are joined to one group. Consequently, if there exist differences in the length of the routing for different signals, there are produced fluctuations in the signal propagation time, i.e., arrival time of signal. These fluctuations in the arrival time of signal is called skew of bus signals. In order to drive a semiconductor device with a high speed, the skew of bus signals should be small. In order to reduce the skew, routing lengths for different signals in the bus signals should be as uniform as possible so that propagation times for different signals are approximately equal to each other.
Heretofore, according to the automatic routing scheme used for routing in an semiconductor device, since the different signals in the bus signals were treated independently as individual signals, the paths were different for the individual signals. For this reason fluctuations in the routing length for different signals in the bus signals were great. Here the path of signal means an assembly of the sub routing areas, through which the routing for that signal passes, when a routing area is divided into a plurality of sub routing areas.
FIG. 3 shows an example of result obtained by a prior art scheme, by which signals are not grouped depending on bus signals, in which routing has been made for a bus signal consisting of 4 signals between terminals of blocks 201, 206, 207 and 208 within a chip 200 and another bus signal consisting of 3 signals between terminals of the blocks 201 and 208 and external terminals. FIG. 3 shows an example of result, in which routing has been made individually for each of the signals belonging to each bus signal. FIG. 10 is a flow chart showing the prior art routing scheme for making the routing indicated in FIG. 3. Block placement information 101 and logical connection information 104 stored in an external memory device 100 are inputted (Step 301). The whole routing area is divided into several sub routing areas on the basis of the block placement information 101 (Step 302). The path for each of the signal is determined on the basis of the logical connection information 104 (Step 305). The routing pattern is determined according to the path (Step 306) and the coordinates of the routing pattern are outputted (Step 307). The result indicated in FIG. 3 is an example, for which routing has been made by choosing the paths so that the numbers of routings for signals passing through different channels are equal to each other. While the paths for signals 202 and 203 pass on the left side of the block 201, the paths for signals 204 and 205 pass on the right side of the block 201. When the paths for the different signals in a bus signal are different in this way, there are produced fluctuations in the length of routing for different signals, which increases the skew of the bus signal.
On the other hand a routing method for bus signals is described in Proc. of Design Automation Conf. (1983) pp 578-583. This literature describes a routing method for a bus signal in an area, which is a closed area enclosed by a continuous broken line and within which there are no obstacles for the routing. However, a routing area is a closed area enclosed by a continuous broken line, within which there exist a number of blocks or inhibited areas as obstacles for routing.